Math 479/Math 560: Optimization

Prof. Andrew Ross

Fall Semester 2024

Basic Information

Note: this syllabus is temporary, and may change up to the first day of class.
This version posted on: 2024-08-23

The official course title is "Introduction to Optimization Theory". However, we will try to split our time evenly between applications/modeling, theory, and methods.

Mathematical optimization is the science (and sometimes art) of finding the best (lowest cost, most lives saved, least risk, or best-fitting) solution to a given minimization or maximization problem. Often, we also try to prove that it is the best, or that it is within some small percentage of the best solution. Some common examples are:

Since you have had the prerequisite courses, you are familiar with finding the minimum or maximum of a function using derivatives (like in first-semester calculus), and finding the minimum or maximum of a function of two or three variables (like in third-semester calculus). In this course, we will be working with thousands of variables--real applications can use millions of variables. Of course, we don't solve problems like that by hand. In our course, we will learn the methods people have developed for computers to solve such large problems.

Official Course Catalog Entry

An introduction to various aspects of optimization theory, including linear and nonlinear programming, primal dual methods, calculus of variations, optimal control theory, sensitivity analysis and numerical methods.

Prerequisites

Completion of courses in elementary linear algebra/matrix algebra and multivariable calculus is assumed.
Some experience using Excel, and Python, Mathematica, Maple, or Matlab/Octave/SciLab will also be very helpful, but it is not strictly a prerequisite.

Follow-up courses: Math 436 Numerical Analysis, Math 419W/519 Stochastic Math Models, various statistics classes.

Related courses:

Class Meetings


Other class info: Math 479 CRN 14657; Math 560 CRN 12766
3 credit hours.

Instructor information

Professor Andrew Ross
Pray-Harrold 515L
andrew.ross@emich.edu
http://emunix.emich.edu/~aross15/
(734) 487-1658, but I strongly prefer e-mail instead of phone contact. During the coronavirus shutdown, my office phone number will just always go to voicemail.
Math department main office: Pray-Harrold 515, (734) 487-1444

Office Hours and other help

In Fall 2024: 
Mon/Wed/Fri: online office hours as shown on my Google Calendar Appointment Calendar
Tue/Thu:
1:15-1:45 office hour in Pray-Harrold 515L
2:00-3:15 Math 319 in Pray-Harrold 321
3:15-4:00 office hour (possibly in Pray-Harrold 321)
4:00-5:15 Math 479/Math 560 in Pray-Harrold 321
5:15-5:45 office hour in Pray-Harrold 515L

You can also make an appointment to meet me on Zoom using my Google Calendar Appointment Page

I am also happy to make appointments if you cannot come to the general office hours. Please send me e-mail to arrange an appointment. It can even be in the evening or on a weekend.

Many assignments in this course will be in the form of papers, which you and I both want to be well written. Please consult with The Writing Center for help in tuning up your writing.

Required materials

We will be using pieces from the following textbooks, which are ELECTRONICALLY FREELY AVAILABLE to EMU students through our campus library:

Other suggested (not required) textbooks are "Operations Research: Applications and Algorithms (4th revised edition)" by Wayne Winston (2004), and "Introduction to Operations Research, 10th edition" by Hillier and Lieberman. These are more undergraduate-level texts, which provide a gentler introduction to the subject but can get stuck in by-hand calculations. The high cost is why they are suggested but not required.

We will also be using software. At least one of the following, and possibly more, is required:

Last time I checked, brand-name Microsoft Excel is available free to EMU students. The University's campus license also allows students, faculty, and staff to install Microsoft Office (Windows, Mac and mobile device versions) at no cost. To obtain the software, login to portal.office.com (Links to an external site.) using your EMU email address (username@emich.edu) and NetID password and then follow the instructions on the page to download and install the application.

Course Web Page

We will use the EMU Canvas system. You are expected to keep an eye on your scores using the system, and get extra help if your scores indicate the need.

Supplementary Materials

Here are some handy web sites: Here are some other optimization books: Other books related to optimization, but not really our main focus: Books on Optimization Models:

Blogs

Here are some of the blogs that relate to our class:

Course Content

Course Goals

Our primary goal is to teach you to be a good (or great!) optimizer. To be a good optimizer, you need:

Our department list of Student Learning Outcomes for Math 560 is: 

Upon successfully completing MATH 560 Introduction to Optimization Theory, students will be able to

Recognize the assumptions that are made in developing a model and how to modify the assumptions to refine the model
Do a project, roughly on the scale of COMAP's Mathematical Contest in Modeling (MCM), and communicate its results
Formulate common Linear, Integer, and Nonlinear programs in software and symbolically
Explain basic solution methods for Linear, Integer, and Nonlinear Programs, including speed considerations
Explain the role of convexity in Nonlinear Programs
Explain meta-heuristics such as Evolutionary methods and Simulated Annealing
Explain duality and sensitivity analysis for LPs and NLPs
Explain other optimization topics such as Constraint Programming, Stochastic Programming, Robust Programming, Dynamic Programming, Calculus of Variations, and Optimal Control
Undergrads enrolled in Math 479 do not need to achieve the same level of ambition in their projects as graduate students in Math 560, and similarly do not need to develop as deep an understanding of some of the solution methods. Here is an idealized, pie-in-the-sky list of more detailed Student Learning Outcomes for this course: Students will be able to:
  1. Formulate common LPs in software and symbolically
  2. Explain the Fundamental Theorem of LP
  3. Formulate common IPs in software and symbolically
  4. Explain other optimization topics: Constraint Programming, Stochastic Programming, Robust Programming, Dynamic Programming, Calculus of Variations, Optimal Control
  5. Explain classic unconstrained NLP solution methods: line search, Steepest Descent, Newton, Quasi-Newton
  6. Explain the roles of convexity in NLPs
  7. Explain meta-heuristics: Evolutionary, Simulated Annealing, and perhaps others
  8. Explain the Simplex Method
  9. Explain duality and sensitivity analysis for LPs; column generation
  10. Explain Lagrange Multipliers/the KKT conditions and sensitivity analysis for constrained NLPs
  11. Explain constrained NLP solution methods
  12. Explain interior-point methods for LP
  13. Explain branch-and-bound for IPs; tight formulations, symmetry-breaking; branch-and-cut
  14. Consider factors affecting speed of unconstrained NLP solution: Conditioning, use of derivatives, algorithm convergence order/rate, etc.
  15. Take an optimization project from initial concept to formulation(s) and solution(s) including algorithmic concerns, and report/presentation.
and we will take them in that order, mostly.

Outline/schedule

Many classes in optimization theory start with linear problems and solution methods, then proceed to nonlinear problems, because linear problems and solution methods are simpler. Other classes start with nonlinear, because then linear is just a special case. We will start with mostly nonlinear problems and solution methods because then you will have a wide base of ideas to do the first (mid-semester) project. See the day-by-day schedule in the file containing All The Homework (or, this direct google doc link in case the bitly link fails) Here is the listing of module topics: 
M010 Introductory Optimization Formulations, Excel Solver, Python intro, Fundamental Theorem of LP
M010a Starter Homework
M010b Linear Algebra Review
M020 Formulating LPs and NLPs: Deeper Dive (incl. networks)
M030 Binary Variables (fun, or not?) and Modeling
M030a Integer Program formulation homework
M030b Algebraic Modeling Languages
M040 Optimization and Society
M050 Intro to Unconstrained NLP: Contours etc.
M060 Learning Rate, SGD etc.
M070 When to Stop, and Line Search
M080 Second-Order Fun! Hessians and Newton's Method
M090 Convexity
M100 How We Solve Linear Programs: Simplex and Interior-Point
M110 (Constrained) LP: Shadow Prices
M120 Constrained NLP: Lagrange Multipliers
M130 Heuristics: Simulated Annealing, Evolutionary methods
M140 Solving Integer Programs: Branch and Bound
Undergraduate (Math 479) students will do fewer homework problems than graduate (Math 560) students.

Grading Policies

Attendance

My lectures and discussions mostly use the document camera, along with demonstrations in Excel and other mathematical software like Python. I do not usually have PowerPoint-like presentations, and thus cannot hand out copies of slides.

Homework

Homework will be assigned about once a week. All homework should be typed unless notified otherwise.

Homework papers should be submitted on-line via EMU Canvas unless otherwise noted in the assignment.

Exams

There will be no exams, unless the class demonstrates an unwillingness to be motivated any other way.

Project(s)

Instead of exams, we will have two projects. Your results for each will reported in a paper and a presentation to the class. You may work by yourself or in a team of 2 people, but no groups larger than 2 will be allowed. You may switch project partners at your will. Your project grades will each be split into roughly: 10 percent for the project proposal (due 2 weeks before the project), 80 percent for the written paper and actual work, and 10 percent for the presentation (subject to change). The presentations for the second project will be made during the time slot reserved for the final exam.

Overall Grades

There is no systematic system for dropping scores like "the lowest 2 homeworks". In the unfortunate event of a need, the appropriate grade or grades may be dropped entirely (at the professor's discretion), rather than giving a make-up. You are highly encouraged to still complete the relevant assignments and consult with me during office hours to ensure you know the material.

Your final score will be computed as follows: Once final scores are computed, a curve will be applied.

General Caveat

The instructor reserves the right to make changes to this syllabus throughout the semester. Notification will be given in class or by e-mail or both. If you miss class, it is your responsibility to find out about syllabus and schedule changes, especially the due dates and times of projects, assignments, or presentations.

Advice from previous students

Last time I taught the course, I asked my students to give advice to you, future students, based on their experiences in my course. Here are some of the highlights:

UNIVERSITY COURSE POLICIES, EXPECTATIONS, AND STUDENT RESOURCES

In addition to the articulated course specific policies and expectation, students are responsible for understanding all applicable university guidelines, policies, and procedures. The EMU Student Handbook is the primary resource provided to students to ensure that they have access to all university policies, support resources, and student's rights and responsibilities. Changes may be made to the EMU Student Handbook whenever necessary, and shall be effective immediately, and/or as of the date on which a policy is formally adopted, and/or the date specified in the amendment. Electing not to access the link provided below does not absolve a student of responsibility. For questions about any university policy, procedure, practice, or resource, please contact the Office of the Ombuds: 248 Student Center, 734.487.0074, emu_ombuds@emich.edu, or visit the website at www.emich.edu/ombuds . CLICK HERE to access the University Course Policies: http://www.emich.edu/studenthandbook/policies/academic.php#univ

Food Pantry

Swoop's Pantry (104 Pierce Hall, emich.edu/swoopspantry, 734 487 4173) offers food assistance to all EMU students who could benefit. Students are able to visit twice per month to receive perishable and non-perishable food items, personal hygiene items, baby items, and more. Students can visit our website for hours of operation and more information. If you are in a position to donate to Swoop's, I encourage you to do so!

Resources

https://www.emich.edu/studenthandbook/campus-resources/index.php

University Writing Center

The University Writing Center Virtual (UWCV) offers writing support to all undergraduate and graduate students. In doing so, we value the diversity of our campus and honor all students and the languages they bring with them to the University. We offer one-to-one writing consulting for both undergraduate and graduate students. The UWC also has several college and program satellite locations across campus. The locations and hours for the other satellites can be found on the UWC web site: http://www.emich.edu/ccw/writing-center/contact.php Students seeking writing support at any UWC location should bring a draft of their writing (along with any relevant instructions or rubrics) to work on during the consultation.

Disabilities Resource Center

The DRC works collaboratively with students, faculty and staff to create an accessible, sustainable, and inclusive educational environment.

University Library

Research support is available to all students, 24/7. This includes getting started with research, identifying sources to search, developing search strategies, evaluating resources, and more. See https://www.emich.edu/library/help/ask.php for all of the ways in which you can get help with research. Some University Library services have changed, and may continue to change, in response to the pandemic. Please check for current information at https://www.emich.edu/library/news/covid.php

Title IX regarding discrimination on the basis of sex

Title IX of the Education Amendments of 1972 prohibits discrimination on the basis of sex under any education program or activity receiving federal financial aid. Sexual assault and sexual harassment is a form of sex discrimination prohibited by Title IX. What you need to know about Title IX

Student and Exchange Visitor Statement (SEVIS):

The Student Exchange Visitor Information System (SEVIS) requires F and J students to report numerous items to the Office of International Students & Scholars (OISS)